package com.aididi.sort;

import java.util.Arrays;
import java.util.Iterator;

/**
 * @Auther: xuzexiang
 * @Date: 2018-10-29 0029 15:42
 * @Description:    快速排序
 *  1）选择一个基准元素,通常选择第一个元素或者最后一个元素
 *  2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
 *  3）此时基准元素在其排好序后的正确位置
 *  4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
 */
public class KuaiSuDemo {

        public static void main(String[] args) {
            int[] array = {4, 3, 6, 9, 7, 1, 2, 4};
            int[] newArr = KuaiSuDemo.quickSort(array, 0, array.length - 1);
            System.out.println(Arrays.toString(newArr));
        }

    /**
     * 获取基准值的位置
     *
     * @param array 待排序数组
     * @param low   起始位置
     * @param hign  终止位置
     * @return
     */
    private static int getReferIndex(int[] array, int low, int hign) {
        //将第一个元素作为参照值
        int referenceValue = array[low];

        while (low < hign) {
            //从后往前找,如果没有找到比基准值小的元素,那么执行hign--
            while (low < hign && array[hign] >= referenceValue) {
                hign--;
            }
            //将比基准值小的值移动到左边
            array[low] = array[hign];

            //从前往后找,如果没有找到比基准值大的元素,那么执行low++
            while (low < hign && array[low] <= referenceValue) {
                low++;
            }
            //将比基准值大的数移动到右边
            array[hign] = array[low];
        }
        array[low] = referenceValue;
        return low;
    }

    /**
     * 快速排序递归实现
     *
     * @param arr  待排序数组
     * @param low  起始位置
     * @param hign 终止位置
     * @return
     */
    public static int[] quickSort(int[] arr, int low, int hign) {
        if (low >= hign) {
            return null;
        }
        int middleIndex = getReferIndex(arr, low, hign);
        //递归对左边的数组(所有比基准值小的元素)进行排序
        quickSort(arr, low, middleIndex - 1);
        //递归对右边的数组(所有比基准值大的元素)进行排序
        quickSort(arr, middleIndex + 1, hign);
        return arr;
    }
}
